跳转至

快速 A/B/n 测试：通过树耦合反馈共享实现精确的多策略比较

文章背景与核心概要

在线平台经常需要评估多种自适应决策策略（如推荐算法、排序系统、定价规则及大语言模型代理），但每一次奖励交互往往伴随着高昂的成本或风险。传统的 A/B/n 测试方法为 \(J\) 个策略中的每一个分配独立的 \(T\) 长度轨迹，导致总样本量达到 \(JT\)，这在资源受限的场景下效率极低。

本文提出了一种名为“树耦合 A/B 测试”（Tree-Coupled A/B Testing, TCAB）的创新设计。该方法通过在每一轮构建一个可预测的树结构，将父子策略间的上下文-动作规律进行最大化耦合，从而在确保每个策略保持其独立有限时域轨迹分布的前提下，实现奖励反馈的共享。研究证明，该方法能显著降低奖励查询次数，在固定 \(J\) 的情况下，其期望查询次数趋近于 \(T+o(T)\)，远优于独立运行的 \(JT\)。实验表明，TCAB 在奖励模型评估、多项选择大模型评估及自适应搜索策略中，显著提升了成本与精度之间的权衡表现。

📌 摘要 (Summary)

在线平台通常需要比较众多的自适应决策策略——例如推荐算法、排序系统、定价规则和语言模型代理——其中每一次奖励交互都带有成本或风险。标准的 A/B/n 测试为 \(J\) 个策略中的每一个分配其独立的 \(T\) 长度轨迹，从而产生 \(JT\) 个总结果。

为了大幅降低这种开销，本文引入了“树耦合 A/B 测试”（TCAB），这是一种针对历史依赖型上下文多臂老虎机策略的精确反馈共享设计。通过在每一轮中通过可预测的树结构最大化耦合父子上下文-动作规律，奖励在匹配的树边组件内共享，同时确保每个策略保留其精确的独立有限时域轨迹规律。该方法显著改善了奖励模型评估、多项选择语言模型评估和自适应搜索策略等应用中的成本-精度边界。

Online platforms often need to compare numerous adaptive decision policies—such as recommendation algorithms, ranking systems, pricing rules, and language-model agents—where every reward interaction carries a cost or risk. Standard \(A/B/n\) testing assigns each of the \(J\) policies its own horizon-\(T\) trajectory, resulting in \(JT\) total outcomes.

To drastically reduce this overhead, this paper introduces Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design for history-dependent contextual-bandit policies. By maximally coupling parent-child context-action laws across a predictable tree structure at each round, rewards are shared among matched tree edges while ensuring every policy retains its precise standalone finite-horizon trajectory law. The approach significantly improves the cost-precision frontier across applications like reward-model evaluation, multi-choice language-model evaluation, and adaptive search policies.

📋 论文摘要 (Abstract)

在线平台日益需要比较多种自适应决策策略——如排序系统、推荐算法、定价规则和语言模型代理——而每一次奖励交互都可能代价高昂或存在风险。直接的 A/B/n 设计为 \(J\) 个策略中的每一个提供其独立的 \(T\) 长度轨迹，因此需要 \(JT\) 个结果。我们引入了树耦合 A/B 测试（TCAB），这是一种针对任意历史依赖型上下文多臂老虎机策略的精确反馈共享设计。在每一轮中，一棵可预测的树连接了当前的策略历史；每个父-子上下文-动作规律都被最大化耦合，并且在每个匹配树边的组件内共享一个奖励。即使这些策略是有意依赖的，每个策略仍保留其精确的独立有限时域轨迹规律。如果 \(D_{e,t}\) 记录了第 \(t\) 轮树边 \(e\) 上的不匹配，则奖励查询次数满足路径恒等式 \(N(T)=T+\sum_{t,e}D_{e,t}\)，因此在期望上等于 \(T\) 加上累积的树边总变差。该成本在所选树上的精确边局部设计中是条件最优的，且当前轮的最小生成树在树设计中是近视最优的。对于固定的 \(J\)，每个策略的次线性伪遗憾和预言机动作的几乎确定唯一性意味着 \(\mathbb{E}[N(T)]=T+o(T)\)，而独立运行则为 \(JT\)。我们还获得了成对策略对比的有限样本方差界。在奖励模型评估、多项选择语言模型评估和自适应搜索策略上的实验证明了成本-精度边界的实质性改进。

Online platforms increasingly compare many adaptive decision policies—ranking systems, recommendation algorithms, pricing rules, and language-model agents—while each reward-bearing interaction can be costly or risky. A direct A/B/n design gives each of \(J\) policies its own horizon-\(T\) trajectory and therefore uses \(JT\) outcomes. We introduce Tree-Coupled A/B Testing (\(\text{TCAB}\)), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies. At each round, a predictable tree connects the current policy histories; every parent--child context--action law is maximally coupled, and one reward is shared within each component of matched tree edges. Every policy retains exactly its standalone finite-horizon trajectory law, even though the policies are deliberately dependent. If \(D_{e,t}\) records a mismatch on tree edge \(e\) at round \(t\), the number of reward queries satisfies the pathwise identity \(N(T)=T+\sum_{t,e}D_{e,t}\) and hence equals \(T\) plus cumulative tree-edge total variation in expectation. This cost is conditionally optimal among exact edge-local designs on the selected tree, and a current-round minimum-spanning tree is myopically optimal among tree designs. For fixed \(J\), sublinear pseudo-regret of every policy and almost-sure uniqueness of the oracle action imply \(\mathbb{E}[N(T)]=T+o(T)\), versus \(JT\) for independent runs. We also obtain finite-sample variance bounds for pairwise policy contrasts. Experiments on reward-model evaluation, multiple-choice language-model evaluation, and adaptive search policies demonstrate substantial improvements in the cost--precision frontier.